#-*- coding: utf-8 -*-
import sys
import math
def merge(A, p, q, r):
    L = [A[i] for i in range(p, q+1)]
    R = [A[j] for j in range(q+1, r+1)]

    L.append(sys.maxint)
    R.append(sys.maxint)
    i = j = 0

    for k in range(p,r+1):
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i+1
        else:
            A[k] = R[j]
            j = j + 1
    pass


def merge_sort(A, p, r):
    if p < r:
        q = int(math.floor((p+r)/2))
        merge_sort(A, p, q)
        merge_sort(A, q+1,r)
        merge(A, p, q, r)

A = [2, 4, 5, 7, 1, 2, 3, 6]
A = [5, 9, 7, 3, 2, 1, 4, 6]
merge_sort(A, 0, len(A)-1)
print A
